/*
2477. 到达首都的最少油耗  https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/
中等  2024/10/18
*/
#include <iostream>
#include <vector>
#include <functional>
using namespace std;
class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        // 构造图的邻接表
        int n = roads.size() + 1;
        vector<vector<int>> graph(n);
        for (const auto& road : roads) {
            int a = road[0], b = road[1];
            graph[a].push_back(b);
            graph[b].push_back(a);
        } 
        // 用来记录每个节点的代表数量
        long long totalFuel = 0;
        // DFS函数，返回当前节点的代表数量
        function<long long(int, int)> dfs = [&](int node, int parent) -> long long {
            long long totalRepresentatives = 1;  // 当前节点的代表数量
            // 遍历所有子节点
            for (int neighbor : graph[node]) {
                if (neighbor != parent) {
                    long long representativesInSubtree = dfs(neighbor, node);
                    // 计算从当前节点到首都所需的油量
                    totalFuel += (representativesInSubtree + seats - 1) / seats;
                    totalRepresentatives += representativesInSubtree;
                }
            }
            return totalRepresentatives;
        };
        // 从首都（0号城市）开始DFS
        dfs(0, -1);
        return totalFuel; 
    }
};

int main() {
    Solution solution;

    // 示例输入：道路和座位数
    vector<vector<int>> roads = {{0, 1}, {1, 2}, {1, 3}, {2, 4}, {2, 5}};  // 这表示有5条路，城市0到1，1到2，1到3，2到4，2到5
    int seats = 2;  // 每辆车最多能坐2个人

    // 调用函数并输出结果
    long long result = solution.minimumFuelCost(roads, seats);
    cout << "最少油耗为: " << result << endl;

    return 0;
}